一、HetGNN [2019]

《Heterogeneous Graph Neural Network》

1. 异质图（heterogeneous graph: HetG）包含多种类型的节点，以及节点之间的多种关系。如下图的学术网络包含了 author 节点、 paper 节点以及 venue 节点，并包含了 author 和 paper 之间的 write 关系、paper 和 paper 之间的 cite 关系、paper 和 venue 之间的 publish 关系。此外，节点还具有属性（author id）以及文本（论文摘要）等特征。异质图的这种普遍性导致大量的研究开始涌入相应的图挖掘方法和算法，例如关系推理（relation inference）、个性化推荐、节点分类等等。

   

   传统的异质图任务中，很多方法都依赖于从手工特征中得到特征向量。这种方式需要分析和计算有关异质图的不同统计特性和属性，从而作为下游机器学习任务的特征向量。但是这种方式仅局限于当前任务，无法推广到其它任务。近期出现的representation learning 方法使得特征工程自动化，从而促进下游的机器学习任务。从同质图开始，graph representation learning 已经扩展到异质图、属性图、以及特定的图。例如：

   • shallow model （如 DeepWalk）最初是为了将图上的短随机游走的集合提供给 SkipGram 模型，从而近似（approximate）这些游走中的节点共现概率（node co-occurrence probability）并获得 node embedding 。

   • 随后，人们提出了语义感知（semantic-aware）方法（如 metapath2vec），从而解决异质图中的节点异质性（node heterogeneity）和关系异质性（relation heterogeneity）。

   • 此外，内容感知方法（如 ASNE）利用latent feature 和属性来学习图中的 node embedding 。

   这些方法直接学习节点的潜在 embedding，但是在捕获丰富的邻域信息方面受到限制。图神经网络 GNN 采用深度神经网络来聚合邻域节点的特征信息，这使得 aggregated embedding 更加强大。此外，GNN 可以自然地应用于 inductive 任务，该任务涉及到训练期间 unseen 的节点。例如，GCN, GraphSAGE, GAT 分别采用卷积操作、LSTM 架构、以及注意力机制来聚合邻域节点的特征信息。GNN 的进步和应用主要集中在同质图上。但是，当前SOTA的 GNN 无法解决异质图学习的以下问题：

   • 问题 C1：异质图中很多节点连接到多种类型的邻居，连接的邻居节点的种类和数量可能各不相同。例如，下图中节点 a 有 5 个直接邻居而节点 c 只有 2 个直接邻居。

     现有的大多数 GNN 仅聚合直接邻域的特征信息，而特征传播过程可能会削弱更远邻域的影响。此外，hub 节点的 embedding 生成受到弱相关的邻居（即，噪声邻居）的影响，并且“冷启动”节点的 embedding 无法充分地被表达（由于邻域信息有限所导致）。

     第一个问题是：如何对每个节点采样和它 embedding 最相关的异质邻居？如下图中的 C1 阶段所示。

   • 问题 C2：异质图中的节点可能具有非结构化的异质内容，如属性、文本、图像等。另外，不同类型节点关联的内容可能有所不同。如下图中：

     • type-1 的节点（如 b,c）关联的内容为属性、文本。

     • type-2 的节点（如 f,g）关联的内容为属性、图像。

     • type-k 的节点（如 d,e）关联的内容为文本、图像。

     当前 GNN 的直接拼接操作或者线性变换操作无法对节点异质内容之间的深层交互（deep interaction）进行建模。而且，由于不同类型节点的内容多种多样，因此针对所有类型节点使用相同的特征变换函数是不合适的。第二个问题是：如何设计节点内容encoder，从而编码异质图中不同节点的内容异质性？如下图中的 C2 阶段所示。

   • 问题 C3：不同类型的邻居对异质图中node embedding 的贡献不同。如学术网络中，author 和 paper 类型的邻居对 author 节点的 embedding 产生更大的影响，因为 venue 类型的节点包含多样化的主题因此具有更 general 的 embedding 。当前大多数 GNN 仅关于同质图，并未考虑节点类型的影响。第三个问题是：如何考虑不同类型节点的影响，从而聚合异质邻居的特征信息。如下图中的 C3 阶段所示。

   

   为解决这些问题，论文 《Heterogeneous Graph Neural Network》 提出了 heterogeneous graph neural network: HetGNN。 HetGNN 是一种用于异质图的 representation learning 图神经网络模型。

   • 首先，作者设计了一种基于重启的随机游走策略，从而对异质图中每个节点采样固定大小的、强相关的异质邻域，并根据节点类型对其进行分组。

   • 然后，作者设计了一个具有两个模块的异质图神经网络体系结构，从而聚合上一步中采样到的邻居的特征信息。

     • 第一个模块采用 RNN 对异质内容的 deep interaction 进行编码，从而获得每个节点的内容 embedding 。

       因为单个节点可能具有多个内容（既有文本又有图像），因此需要通过一个模块来融合多种不同的内容从而得到内容 embedding 。

     • 第二个模块采用另一个 RNN 来聚合不同分组邻居的内容 embedding，然后通过注意力机制将其进一步组合，从而区分不同异质节点类型的影响，并获得最终 embedding 。

   • 最后，论文利用图上下文损失（ graph context loss）和 mini-batch 随机梯度下降来训练模型。

   总而言之，论文的主要贡献：

   • 论文形式化了异质图 representation learning的问题，该问题涉及到图结构异质性和节点内容异质性。

   • 论文提出了一种创新的异质图神经网络模型（heterogeneous graph neural network model: HetGNN），用于异质图上的 representation learning 。HetGNN 能够捕获结构异质性和内容异质性，并对 transductive task 和 inductive task 都很有用。下表总结了 HetGNN 与最近的一些模型（包括同质图模型、异质图模型、属性图模型、以及图神经网络模型）相比的主要优势。

     

   • 论文在几个公共数据集上进行了广泛的实验，结果表明：HetGNN 在各种图数据挖掘任务（链接预测、推荐、节点分类、聚类）中可以超越 SOTA 的 baseline 方法。

2. 相关工作：

   • 异质图挖掘（heterogeneous graph mining）：在过去的十年中，许多工作致力于挖掘异质图从而用于不同的 application ，如关系推断、个性化推荐、节点分类等等。

     • 《When will it happen?: relationship prediction in heterogeneous information networks》 利用 metapath-based 方法来抽取拓扑特征并预测学术图academic graph中的引用关系。

     • 《Task-Guided and Path-Augmented Heterogeneous Network Embedding for Author Identification》 设计了一个基于异质图的 ranking model 来识别匿名论文的作者。

     • 《Deep Collective Classification in Heterogeneous Information Networks》 提出了一种深度卷积分类模型，用于异质图中的 collective classification 。

   • 图表示学习（graph representation learning）：graph epresentation learning 已经成为过去几年最流行的数据挖掘主题之一。人们提出了基于图结构的模型来学习向量化的 node embedding 从而进一步用于下游各种图挖掘任务。

     • 受到 word2vec 的启发，《Deepwalk: Online learning of social representations》 创新性地提出了 DeepWalk，它在图中引入了 node-context 的概念（类比于 word-context），并将图上的随机游走的集合（类比于 sentence 集合）提供给 SkipGram 从而获得 node embedding 。

     • 后来，为了解决图结构的异质性，《metapath2vec: Scalable Representation Learning for Heterogeneous Networks》 引入了 metapath-guided 随机游走，并提出 metapath2vec 模型来用于异质图中的 representation learning 。

     • 此外，人们已经提出了属性图嵌入模型（《Attributed network embedding for learning in a dynamic environment》、《Attributed social network embedding》、《SHNE: Representation Learning for Semantic-Associated Heterogeneous Networks》）来利用图结构和节点属性来学习 node embedding 。

     • 除了这些方法之外，人们还提出了许多其它方法（《Heterogeneous network embedding via deep architectures》、《Hierarchical Taxonomy Aware Network Embedding》、《Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec》、《Pte: Predictive text embedding through large-scale heterogeneous text networks》、《Learning Deep Network Representations with Adversarially Regularized Autoencoders》）。

   • 图神经网络（graph neural networks）：最近，随着深度学习的出现，图神经网络获得了很多关注。与之前的 graph embedding 模型不同，GNN 背后的关键思想是：通过神经网络从节点的局部邻域中聚合特征信息。

     • Graph-SAGE 使用神经网络（如 LSTM）来聚合邻域的特征信息。

     • GAT 使用自注意力机制来衡量不同邻居的影响力，并结合它们的影响力来获得 node embedding 。

     • 此外，人们已经提出了一些 task dependent 的方法从而为特定任务获得更好的 node embedding ，例如用于恶意账户检测的 GEM （《Heterogeneous Graph Neural Networks for Malicious Account Detection》）。

1.1 模型

1. 定义一个带内容的异质图（content associated heterogeneous graph:C-HetG）为 $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{A},\mathcal{R})$$\mathcal G = (\mathcal V,\mathcal E,\mathcal A,\mathcal R)$ ，其中 $\mathcal{V}$$\mathcal V$ 为节点集合， $\mathcal{E}$$\mathcal E$ 为边集合， $\mathcal{A}$$\mathcal A$ 为节点类型集合， $\mathcal{R}$$\mathcal R$ 为关系类型集合。图中每个节点关联了异质内容信息，例如属性（attribute）、文本（text）、图像（image）。

   给定一个 C-HetG $\mathcal{G}$$\mathcal G$ ，以及节点内容信息，异质图表示学习（Heterogenous Graph Representation Learning）的目标是设计一个模型 ${\mathcal{F}}_{\mathrm{\Theta }}$$\mathcal F_\Theta$ 来学习每个节点的 embedding ，从而能够同时编码异质结构信息和异质内容信息，其中 $\mathrm{\Theta }$$\Theta$ 为模型参数。

   学到的 node embedding 可以应用于下游各种图挖掘任务，如链接预测、推荐、多标签分类、节点聚类等。

2. 我们首先给出 HetGNN 的整体框架如下图所示，其中包含四个部分：对异质邻居节点进行采样、编码节点的异质内容、聚合节点的异质邻居、定义目标函数并给出训练过程。

   下图中：

   • 图 (a) 为整体框架：

     • 首先为每个节点（以节点 a 为例）采样固定数量的异质邻居节点。

     • 然后通过 NN-1 神经网络编码每个节点的异质内容。

     • 然后通过 NN-2 神经网络和 NN-3 神经网络来聚合采样到的异质邻居节点的内容 embedding。

     • 最后通过图上下文损失函数来优化模型。

   • 图 (b) 为NN-1 神经网络，它是节点异质内容编码器。

   • 图 (c) 为 NN-2 神经网络，它是 type-based 邻域聚合器。

   • 图 (d) 为 NN-3 神经网络，它是异质类型组合器。

   

1.1.1 异质邻居采样

1. 大多数神经网络GNN 的关键思想是聚合来自节点的直接邻居（一阶邻居）的特征信息，如 GraphSAGE 或 GAT。但是，直接将这些方法应用到异质图可能会引起一些问题：

   • 它们无法从不同类型的异质邻居的直接链接中捕获充分的信息。如，在学术网络中，author 并未和其它 author 或 venue 直接相连，但是可能存在间接连接。如果仅考虑直接连接的邻居，则可能导致学到的 representation 表达能力不足。

   • embedding 可能受到不同邻居规模的影响。如在推荐常见中，某些 item 和很多用户交互，另一些 item 可能只有很少的用户交互。因此：某些热门节点的 embedding 可能会被某些弱相关的邻居而损害，而一些冷门节点的 embedding 可能未能充分学习。

   • 无法直接聚合具有不同内容特征的异质邻居。异质邻居的内容可能需要不同的特征变换，从而处理不同的特征类型和特征维度。

   针对这些问题并解决问题 C1，我们设计了一种基于重启的随机游走策略（random walk with restart: RWR）来对异质邻居进行采样。

   RWR 包含两个连续的步骤：

   • step1 ：基于 RWR 采样固定数量的邻居。我们从节点 $v\in \mathcal{V}$$v\in \mathcal V$ 开始随机游走，它以概率 $p$$p$ 回到起始节点 $v$$v$ 或者以概率 $1-p$$1-p$ 游走到下一个相连的节点。

     我们始终执行 RWR 直到收集到固定数量的节点，收集到的节点集合记作 $\text{RWR}(v)$$\text{RWR}(v)$ 。

     注意：$\text{RWR}(v)$$\text{RWR}(v)$ 中不同类型节点的数量受到限制，从而确保为节点 $v$$v$ 采样到所有类型的邻居节点。如，类型 $t\in \mathcal{A}$$t\in \mathcal A$ 的邻居节点限制为 $K_t$$K_t$ 个。

   • step2：对采样的邻居节点集合根据节点类型进行分组。对于节点类型 $t\in \mathcal{A}$$t\in \mathcal A$ ，我们根据频次从 $\text{RWR}(t)$$\text{RWR}(t)$ 中选择 top $k_t$$k_t$ 个节点（$k_t\le K_t$$k_t\le K_t$），并将选中的这些节点作为节点 $v$$v$ 关于类型 $t$$t$ 的强相关邻居的集合。

   由于下列原因，RWR 策略能够避免上述问题：

   • RWR 能够为每个节点收集到所有类型的邻居。

   • 每个节点采样的邻居规模是固定的，并且访问最频繁的邻居节点（即最相关的）被挑选出来。

   • 根据节点类型对邻居进行分组（每个分组具有相同的内容格式），以便可以设计基于类型的聚合。

1.1.2 异质内容编码

1. 我们设计了一个具有两个模块的异质图神经网络体系结构，从而聚合每个节点的采样后异质邻居的特征信息。

2. 为解决问题 C2，我们设计了一个模块，从节点 $v\in \mathcal{V}$$v\in \mathcal V$ 中提取异质内容 $C_v$$C_v$ ，并通过神经网络 $f_1$$f_1$ 将其编码为固定大小的 embedding 。

   具体而言，我们将 $C_v$$C_v$ 中的第 $i$$i$ 个内容（每个节点可能包含多个内容，如文本、图像、属性等）的特征表示为 ${\overrightarrow{\mathbf{x}}}_{v,i}\in {\mathbb{R}}^{d_c}$$\mathbf{\vec x}_{v,i}\in \mathbb R^{d_c}$ ，其中 $d_c$$d_c$ 为内容特征的维度。注意：${\overrightarrow{\mathbf{x}}}_{v,i}$$\mathbf{\vec x}_{v,i}$ 可以通过针对不同类型的内容采取不同的技术来预训练得到。如，可以利用 Par2Vec 来预训练文本内容，可以利用 CNN 来预训练图像内容。

   之前的一些方法直接拼接不同的内容特征，或者将不同的内容特征经过线性映射到相同的特征空间。和这些方法不同，我们基于 Bi-LSTM 设计了一种新的架构来捕获 deep feature interaction，并获得更强的表达能力。

   因此，节点 $v$$v$ 的内容 embedding 为：

   $${\overrightarrow{\mathbf{z}}}_v=f_1(v)=\frac{\sum _{i\in C_v}[\overrightarrow{\text{LSTM}}\{{\mathcal{F}}_C({\overrightarrow{\mathbf{x}}}_{v,i};{\theta }_x)\}⨁\overleftarrow{\text{LSTM}}\{{\mathcal{F}}_C({\overrightarrow{\mathbf{x}}}_{v,i};{\theta }_x)\}]}{|C_v|}$$

   其中：

   • ${\overrightarrow{\mathbf{z}}}_v\in {\mathbb{R}}^d$$\mathbf{\vec z}_v\in \mathbb R^d$ 为节点 $v$$v$ 的内容 embedding， $d$$d$ 为内容 embedding 维度。

   • ${\mathcal{F}}_C(\cdot ;{\theta }_x)$$\mathcal F_C(\cdot;{\theta_x})$ 为特征变换器（feature transformer），它可以是恒等映射（没有任何变换）、也可以是一个全连接神经网络（参数为 ${\theta }_x$$\theta_x$ ）。即，在将 ${\overrightarrow{\mathbf{x}}}_{v,i}$$\mathbf{\vec x}_{v,i}$ 灌入到 LSTM 之前，首先进行特征变换。

   • $⨁$$\bigoplus$ 表示拼接操作。

   具体而言，上述架构首先使用不同的 FC 层来转换不同的内容特征，然后使用 Bi-LSTM 来捕获 deep feature interaction，并聚合所有内容特征的表达能力。最后取所有隐状态的均值来获得节点 $v$$v$ 的内容 embedding 。

   通过内容拼接然后馈入全连接层也可以捕获 deep feature interaction 。这里用 Bi-LSTM 个人觉得不太合理，因为 Bi-LSTM 强调有序的输入，而这里的输入是无序的。虽然通过随机排列内容集合 $C_v$$C_v$ 从而应用到 Bi-LSTM 中，但是这仅仅是一种变通方案，而没有很好地捕获到内容信息之间的关联（如互补关系、overlap 关系）。

   注意：

   • Bi-LSTM 应用在无序的内容集合 $C_v$$C_v$ 上，这是受到 GraphSAGE 在聚合无序邻居的启发。

   • 我们使用不同的 Bi-LSTM 来聚合不同类型节点的内容特征，因为它们的内容类型互不相同。

3. 上述内容 embedding 体系结构有三个主要优点：

   • 具有较低复杂度的间接架构（参数较少），使得模型的实现和调整都相对容易。

   • 能够融合异质内容信息，具有很强的表达能力。

   • 增加额外的特征很灵活，使得模型扩展很方便。

1.1.3 异质邻居聚合

1. 为聚合每个节点的异质邻居的内容 embedding（问题 C3），我们设计了另一个type-based 神经网络模块，它包含两个步骤：同一类型的邻居聚合、类型组合。

2. 同一类型的邻居聚合：我们使用基于 RWR 的策略为每个节点采样固定数量的、包含不同类型的邻居集合，并针对类型 $t$$t$ 选中 top $k_t$$k_t$ 的异质邻居，记作 ${\mathcal{N}}_t(v)$$\mathcal N_t(v)$ 。然后，我们使用神经网络 $f_2^t$$f_2^t$ 来聚合 ${\mathcal{N}}_t(v)$$\mathcal N_t(v)$ 中邻居节点的 embedding ：

   $${\overrightarrow{\mathbf{n}}}_v^t=f_2^t(v)={\text{AGG}}_{u\in {\mathcal{N}}_t(v)}^t\left\{{\overrightarrow{\mathbf{z}}}_u\right\}$$

   其中：

   • ${\overrightarrow{\mathbf{n}}}_v^t\in {\mathbb{R}}^d$$\mathbf{\vec n}_v^t \in \mathbb R^d$ 为节点 $v$$v$ 类型为 $t$$t$ 的邻居聚合后的 embedding 向量， $d$$d$ 为聚合后的内容 embedding 维度。

   • ${\text{AGG}}^t(\cdot )$$\text{AGG}^t(\cdot)$ 为类型为 $t$$t$ 的邻域聚合函数，可以是全连接网络、CNN 网络、或者是 RNN 网络。

     这里我们选中 ${\text{AGG}}^t(\cdot )$$\text{AGG}^t(\cdot)$ 为 Bi-LSTM，因为实践中它的效果最好。因此：

     $${\overrightarrow{\mathbf{n}}}_v^t=\frac{\sum _{u\in {\mathcal{N}}^t(v)}[\overrightarrow{\text{LSTM}}\left\{{\overrightarrow{\mathbf{z}}}_u\right\}⨁\overleftarrow{\text{LSTM}}\left\{{\overrightarrow{\mathbf{z}}}_u\right\}]}{|{\mathcal{N}}_t(v)|}$$

     我们使用 Bi-LSTM 聚合所有类型为 $t$$t$ 的邻居，并使用所有隐状态的均值作为最终聚合的 embedding 。

     注意：

     • 我们使用 Bi-LSTM 来区分不同节点类型的邻域聚合。

     • Bi-LSTM 应用在无序邻居上，这是受到 GraphSAGE 在聚合无序邻居的启发。

3. 类型组合（type combination）：前面为每个节点 $v$$v$ 生成了 $|\mathcal{A}|$$|\mathcal A|$ 个聚合embedding $\{{\overrightarrow{\mathbf{n}}}_v^1,\cdots ,{\overrightarrow{\mathbf{n}}}_v^{|\mathcal{A}|}\}$$\left\{\mathbf{\vec n}_v^1,\cdots,\mathbf{\vec n}_v^{|\mathcal A|} \right\}$ 。为了结合这些 type-based 邻域聚合 embedding 以及节点的内容 embedding，我们采用了注意力机制。我们认为：不同类型的邻域对 $v$$v$ 的 final embedding 做出的贡献不同。因此，节点 $v$$v$ 的最终 embedding 为：

   $${\overrightarrow{\mathbf{h}}}_v={\alpha }^{v,v}{\overrightarrow{\mathbf{z}}}_v+\sum _{t\in \mathcal{A}}{\alpha }^{v,t}{\overrightarrow{\mathbf{n}}}_v^t$$

   其中：

   • ${\overrightarrow{\mathbf{h}}}_v\in {\mathbb{R}}^d$$\mathbf{\vec h}_v\in \mathbb R^{d}$ 为节点 $v$$v$ 的 final embedding 。

   • ${\alpha }^{v,\ast }$$\alpha^{v,*}$ 给出了不同embedding 的重要性。

   • ${\overrightarrow{\mathbf{z}}}_v$$\mathbf{\vec z}_v$ 为节点 $v$$v$ 的内容 embedding， ${\overrightarrow{\mathbf{n}}}_v^t$$\mathbf{\vec n}_v^t$ 为节点 $v$$v$ 的类型为 $t$$t$ 的邻域聚合 embedding 。

   定义节点 $v$$v$ 的所有 embedding 集合为 $\mathcal{F}(v)=\{{\overrightarrow{\mathbf{z}}}_v,{\overrightarrow{\mathbf{n}}}_v^1,\cdots ,{\overrightarrow{\mathbf{n}}}_v^{|\mathcal{A}|}\}$$\mathcal F(v) = \left\{\mathbf{\vec z}_v, \mathbf{\vec n}_v^1,\cdots,\mathbf{\vec n}_v^{|\mathcal A|}\right\}$ ，则有：

   $${\alpha }^{v,i}=\frac{\exp \left(\sigma (\overrightarrow{\mathbf{u}}\cdot [{\overrightarrow{\mathbf{f}}}_i⨁{\overrightarrow{\mathbf{z}}}_v])\right)}{\sum _{{\overrightarrow{\mathbf{f}}}_j\in \mathcal{F}(v)}\exp \left(\sigma (\overrightarrow{\mathbf{u}}\cdot [{\overrightarrow{\mathbf{f}}}_j⨁{\overrightarrow{\mathbf{z}}}_v])\right)}$$

   其中：

   • $\sigma (\cdot )$$\sigma(\cdot)$ 为激活函数，这里我们选择 LeakyReLU。

   • ${\overrightarrow{\mathbf{f}}}_i\in \mathcal{F}(v)$$\mathbf{\vec f}_i\in \mathcal F(v)$ 为 $\mathcal{F}(v)$$\mathcal F(v)$ 中的第 $i$$i$ 个 embedding 向量。

   • $\overrightarrow{\mathbf{u}}\in {\mathbb{R}}^{2d}$$\mathbf{\vec u}\in \mathbb R^{2d}$ 为注意力向量（attention vector），是待学习的参数。

4. 在整个框架中，为了使得 embedding 维度一致并且模型易于调整，我们使用相同的维度 $d$$d$ 来作用于内容 embedding、节点邻域聚合 embedding、节点 final embedding 。

1.1.4 模型训练

1. 为学习异质图的 node embedding，我们定义目标函数为：

   $$\mathcal{L}=\prod _{v\in \mathcal{V}}\prod _{t\in \mathcal{A}}\prod _{v_c\in {\mathcal{C}}_v^t}p(v_c\mid v;\mathrm{\Theta })$$

   其中：

   • ${\mathcal{C}}_v^t$$\mathcal C_v^t$ 为节点 $v$$v$ 在异质图中类型为 $t$$t$ 的邻域中的上下文（即窗口大小为 $c$$c$ 之内的邻居节点）。

   • 条件概率 $p(v_c\mid v;\mathrm{\Theta })$$p(v_c\mid v;\Theta)$ 定义为异质 softmax 函数：

     $$p(v_c\mid v;\mathrm{\Theta })=\frac{\exp ({\overrightarrow{\mathbf{h}}}_{v_c}\cdot {\overrightarrow{\mathbf{h}}}_v)}{\sum _{v_k\in {\mathcal{V}}_t}\exp ({\overrightarrow{\mathbf{h}}}_{v_k}\cdot {\overrightarrow{\mathbf{h}}}_v)}$$

     ${\mathcal{V}}_t$$\mathcal V_t$ 为异质图中类型为 $t$$t$ 的所有节点集合， ${\overrightarrow{\mathbf{h}}}_v$$\mathbf{\vec h}_v$ 为节点 $v$$v$ 的 final embedding 。

2. 我们利用负采样技术来调整目标函数，此时 $p(v_c\mid v;\mathrm{\Theta })$$p(v_c\mid v;\Theta)$ 为：

   $$p(v_c\mid v;\mathrm{\Theta })=\log \sigma ({\overrightarrow{\mathbf{h}}}_{v_c}\cdot {\overrightarrow{\mathbf{h}}}_v)+\sum _{m=1}^M{\mathbb{E}}_{v_{c^{\prime }}\sim P_t(v_{c^{\prime }})}\log \sigma (-{\overrightarrow{\mathbf{h}}}_{v_{c^{\prime }}}\cdot {\overrightarrow{\mathbf{h}}}_v)$$

   其中：

   • $P_t(v_{c^{\prime }})$$P_t(v_{c^\prime})$ 为预先给定的、针对节点类型 $t$$t$（与 $v_c$$v_c$ 类型相同） 的噪音分布 noise distributioin 。

   • $M$$M$ 为负采样数量，这里我们选择 $M=1$$M=1$ ，因为我们发现选择 $M>1$$M\gt 1$ 对于最终效果影响很小。因此上式降级为交叉熵损失函数：

     $$p(v_c\mid v;\mathrm{\Theta })\simeq \log \sigma ({\overrightarrow{\mathbf{h}}}_{v_c}\cdot {\overrightarrow{\mathbf{h}}}_v)+\log \sigma (-{\overrightarrow{\mathbf{h}}}_{v_{c^{\prime }}}\cdot {\overrightarrow{\mathbf{h}}}_v)$$

     即：对于节点 $v$$v$ 的每个上下文节点 $v_c$$v_c$ （类型为 $t$$t$ ），我们根据分布 $P_t(v_{c^{\prime }})$$P_t(v_{c^\prime})$ 针对节点类型 $t$$t$ 采样一个负样本 $v_{c^{\prime }}$$v_{c^\prime}$ 。

   最终我们的损失函数为：

   $$\mathcal{L}=\sum _{<v,v_c,v_{c^{\prime }}>\in T_{\text{walk}}}[\log \sigma ({\overrightarrow{\mathbf{h}}}_{v_c}\cdot {\overrightarrow{\mathbf{h}}}_v)+\log \sigma (-{\overrightarrow{\mathbf{h}}}_{v_{c^{\prime }}}\cdot {\overrightarrow{\mathbf{h}}}_v)]$$

   其中 $T_{\text{walk}}$$T_\text{walk}$ 表示通过图上的随机游走收集到的 $<v,v_c,v_{c^{\prime }}>$$<v,v_c,v_{c^\prime}>$ 三元组的集合。

   注意，$v_c$$v_c$ 和 $v_{c^{\prime }}$$v_{c^\prime}$ 都是类型为 $t$$t$ 。此外，这里仅考虑无监督损失，并未考虑监督损失。

3. 类似于DeepWalk，我们设计了一个随机游走过程来生成 $T_{\text{walk}}$$T_\text{walk}$ ：

   • 首先，我们在异质图中统一生成一组随机游走序列的集合 $\mathcal{S}$$\mathcal S$ 。

   • 然后，对于随机游走序列集合 $\mathcal{S}$$\mathcal S$ 中的第 $i$$i$ 条随机游走序列 $S_i$$S_i$ ，对于序列中的每个节点 $v$$v$ ，我们收集上下文窗口 $c$$c$ 内的每个上下文节点 $v_c$$v_c$ 。

   • 最后，对于每个上下文节点 $v_c$$v_c$ ，我们以概率分布 $P_t(v_{c^{\prime }})\propto g_{v_{c^{\prime }}}^{3/4}$$P_t(v_{c^\prime})\propto g_{v_{c^\prime}}^{3/4}$ 来采样一个和 $v_c$$v_c$ 相同类型的负样本 $v_{c^{\prime }}$$v_{c^\prime}$。 $g_{v_{c^{\prime }}}$$g_{v_{c^\prime}}$ 为节点 $v_{c^{\prime }}$$v_{c^\prime}$ 的 degree ，也等于它在 $\mathcal{S}$$\mathcal S$ 中出现的频次。

4. 在训练的每轮迭代中，我们对 $T_{\text{walk}}$$T_\text{walk}$ 随机采样 mini-batch 的三元组，然后通过 Adam 优化器来更新模型参数。我们反复迭代直到模型收敛为止。

1.2 实验

1. 这里我们进行广泛的实验：

   • HetGNN 在各种图挖掘任务中和 SOTA baseline 方法的比较，如链接预测、个性化推荐、节点分类&聚类任务。

   • HetGNN 在 inductive learning 任务中和 SOTA baseline 方法的比较，如 inductive 节点分类&聚类任务。

   • HetGNN 中不同组件（如异质节点内容编码器，异质邻域聚合器）对模型性能的影响。

   • HetGNN 中各种超参数（如embedding 维度、异质邻居采样大小）对模型性能的影响。

2. 数据集：我们采用两种异质图数据集：学术图（academic graph）、评论图（review graph）。

   • 学术图：我们从 AMiner 数据集中抽取两个数据集：

     • A-I 包含 1996 ~ 2005 年之间计算机科学会议的论文。

     • A-II 包含 2006 ~ 2015 年之间若干个人工智能和数据科学相关的顶会的论文，因为考虑到大多数研究人员关注于顶会的论文。

     每篇论文都有各种内容信息，包括：标题、摘要、作者、参考文献、年份、所属会议。

   • 评论图：我们从公开的 Amazon 数据集抽取了两个数据集，即 R-I（电影类别的评论）、R-II（CD 类别的评论）。数据集包含 1996-05 ~ 2014-07 之间用户的评论信息、商品元数据信息。

     每个商品都有各种内容信息，包括：标题、描述文本、类型、价格、图片。

   下表给出了这四个数据集的主要统计信息：

   

3. 内容特征编码：

   • 在学术网络中，我们使用 ParVec 预训练论文的标题和摘要。此外，我们还使用 DeepWalk 来预训练异质图中所有节点的 embedding （将异质图视为同质图来训练）。

     • 每个作者节点关联一个预训练的 author embedding （通过 DeepWalk 得到）、作者的所有论文（经过采样之后）的论文摘要 embedding 均值（通过 ParVec 得到）、作者的所有论文（经过采样之后）的论文标题 embedding 均值。因此，作者的内容编码器的 Bi-LSTM 的长度为 3 。

     • 每篇论文关联一个预训练的 paper embedding （通过 DeepWalk 得到）、论文的摘要 embedding（通过 ParVec 得到）、论文的标题 embedding （通过 ParVec 得到）、论文作者预训练 embedding 的均值（通过 DeepWalk 得到，一篇论文可能有多个作者）、论文会议的预训练 embedding （通过 DeepWalk 得到）。因此，论文的内容编码器的 Bi-LSTM 的长度为 5 。

     • 每个会议节点关联一个预训练的会议 embedding（通过 DeepWalk 得到）、会议中随机抽取的论文的摘要的平均 embedding（通过 ParVec 得到）、会议中随机抽取的论文的标题的平均 embedding （通过 ParVec 得到）。因此，会议的内容编码器的 Bi-LSTM 的长度为 3 。

   • 在评论网络中，我们使用 ParVec 预训练商品标题和描述内容，用 CNN 预训练商品图片。此外，我们还使用 DeepWalk 来预训练异质图中所有节点的 embedding （将异质图视为同质图来训练）。

     • 每个用户关联一个预训练的用户 embedding （通过 DeepWalk 得到）、所有用户评论过的（经过采样之后）商品的描述文本 embedding 均值（通过 ParVec 得到）、所有用户评论过的（经过采样之后）商品的图片 embedding 均值（通过 CNN 得到）。因此，用户的内容编码器的 Bi-LSTM 长度为 3 。

     • 每个商品关联一个预训练的 item embedding（通过 DeepWalk 得到）、商品描述文本的 embedding （通过 ParVec 得到）、商品图片的 embedding （通过 CNN 得到）。因此，商品的内容编码器的 Bi-LSTM 长度为 3 。

4. baseline 方法：我们使用5 个 baseline，包括异质图 embedding 模型、属性网络模型、图神经网络模型。

   • metapath2vec: MP2V：一个异质图 embedding 模型，它基于 metapath 指导的随机游走来生成随机游走序列，并通过 SkipGram 模型来学习node embedding 。

   • ASNE：一种属性网络 embedding 方法，它使用节点的潜在特征和属性来学习node embedding 。

   • SHNE：一种属性网络 embedding 方法，它通过联合优化图结构邻近性和文本语义相似性，从而学习文本相关的异质图的node embedding 。

   • GraphSAGE：一个图神经网络模型，它聚合了邻居的特征信息。

   • GAT：一个图注意力网络模型，它通过 self-attention 机制来聚合邻居的特征信息。

5. HetGNN 的参数配置：

   • embedding 维度为 128 。

   • 邻域采样规模：

     • 对于学术网络，邻域采样大小为 23，其中作者节点选择 top-10、论文节点选择 top-10、会议节点选择 top-3 。

     • 对于评论网络，邻域采样大小为 20，其中用户节点选择 top-10、商品节点选择 top-10 。

   • 对于 RWR，我们选择返回概率 $p=0.5$$p=0.5$ ，每个节点的 RWR 序列长度为 100 （即 $|RWR(v)|=100$$|RWR(v)| = 100$） 。

   • 在获取三元组集合 $T_{\text{walk}}$$T_\text{walk}$ 时，每个节点开始的随机游走序列数量为 10，每条随机游走序列长度为 30，上下文窗口大小为 5 。

   • 我们使用 Pytorch 来实现 HetGNN，并在 GPU 上进行实验。

6. baseline 参数配置：

   • 为公平起见，所有 baseline 的维度设为 128 。

   • 对于 metapath2vec，对于学术网络我们使用三个 metapath：APA（author-paper-author)、 APVPA(author-paper-venue-paper-author)、APPA(author-paper-paper-author) ；对于评论网络我们使用一个 metapath：UIU(user-item-user) 。

     每个节点开始的随机游走序列数量为 10，每条随机游走序列的长度为 30 ，这和 HetGNN 保持一致。

   • 对于 ASNE，除了 latent 特征之外，我们使用 HetGNN 相同的内容特征，然后将它们拼接为一个通用的属性特征。

   • 对于 SHNE，对于两个数据集我们分别利用论文摘要和商品描述（文本序列 = 100 ）作为 deep semantic 编码器（如 LSTM）的输入。此外，随机游走序列的配置和 metapath2vec 相同。

   • 对于 GraphSAGE 和 GAT，我们使用HetGNN 相同的内容特征作为输入特征（拼接为一个通用的属性特征），并将每个节点的采样邻居数量设为和 HetGNN 相同。

1.2.1 链接预测

1. 之前的做法是：随机采样一部分链接进行训练，然后使用剩余链接用于预测。我们认为应该根据时间顺序来拆分训练集和测试集，而不是随机拆分。

   • 对于学术图，我们令 $T_s$$T_s$ 为拆分年份，则 $T_s$$T_s$ 之前的是训练集， $T_s$$T_s$ 之后的是测试集。

     对于 A-I 数据集，我们考虑两种拆分情况：$T_s=2003$$T_s = 2003$ 或 $T_s=2002$$T_s = 2002$ ；对于 A-II 数据集，我们也考虑两种拆分情况：$T_s=2013$$T_s = 2013$ 或 $T_s=2012$$T_s = 2012$ 。

     另外，对于学术图我们仅考虑两种类型的边：作者之间的共同撰写关系(type-1)、作者和论文之间的引用关系（type-2）。

   • 对于评论图，我们按顺序拆分。对于 R-I 数据集，根据边的数量拆分比例为 7:3 ，对于 R-II 数据集，根据边的数量拆分比例为 5:5 。

   对于测试集：

   • 删除测试集中重复的边。

   • 随机采样相等数量的“负边”（即不存在的噪音边）加入测试集。

   我们使用所有节点 + 训练集的边来学习node embedding，然后使用训练集的链接来训练逻辑回归分类器。逻辑回归分类器的输入为边的 embedding ，每条边的 embedding 是两端node embedding 的逐元素乘积。

   最后，我们使用训练好的分类器来评估测试集，评估指标为 AUC 和 F1-Score 。

2. 链接预测结果见下表所示，其中最佳结果以粗体突出显示。

   结论：

   • 大多数情况下，最好的 baseline 是属性图 embedding 方法或图神经网络方法，这表明融合节点属性或使用深度神经网络能产生更好的node embedding，从而有利于链接预测。

   • 在所有情况下，尤其是评论图中，HetGNN 均优于所有 baseline 方法。这证明了HetGNN 是有效的，它产生了针对链接预测任务更有效的node embedding 。

   

1.2.2 个性化推荐

1. 我们在学术图中评估顶会推荐 (author-venue 链接) 的表现。具体而言，训练数据用于学习node embedding。推荐的ground-truth 为：给定测试集中的顶会，作者在测试数据集中出现（发表过论文）。

   和链接预测任务相同，对于 A-I 数据集，我们考虑两种拆分情况：$T_s=2003$$T_s = 2003$ 或 $T_s=2002$$T_s= 2002$ ；对于 A-II 数据集，我们也考虑两种拆分情况：$T_s=2013$$T_s = 2013$ 或 $T_s=2012$$T_s = 2012$ 。

   我们采用两个节点的 embedding 内积作为推荐分，并挑选 top-k 推荐分的作者作为推荐列表。对于A-I 数据集，k=5；对于 A-II 数据集， k=3。

   推荐的评估指标为 top-k 推荐列表的 Recall(Rec), Precision(Pre), F1-Score ，最终我们给出所有作者的均值作为报告得分。此外，重复的 author-venue pair 将从评估中删除。

2. 个性化推荐结果见下表所示，其中最佳结果以粗体突出显示。

   结论：

   • 大多数情况下，最好的 baseline 是属性图 embedding 方法或图神经网络方法，这表明融合节点属性或使用深度神经网络能产生更好的node embedding，从而有利于个性化推荐。

   • 在所有情况下，尤其是评论图中，HetGNN 均优于所有 baseline 方法。这证明了HetGNN 是有效的，它产生了针对个性化推荐任务更有效的node embedding 。

   

1.2.3 节点分类&聚类

1. 类似 metapath2vec，我们将 A-II 数据集中的作者分类到四个选定的研究领域：数据挖掘（ data mining:DM）、计算机视觉（computer vision:CV）、自然语言处理（natural language processing:NLP）、数据库（databse:DB）。

   具体而言，我们为每个领域选择三个热门会议，每个作者标记为他/她大部分论文所属的领域。如果在这些会议中未发表论文的作者将被剔除评估。如果作者在这些会议的多个领域发表过论文，则作者为多个标签。因此这是一个多标签节点分类问题。

   我们从完整数据集中学习node embedding，然后将学到的node embedding 来作为逻辑回归分类器的输入。我们将带标记的节点随机拆分，训练集的大小从 10%~30%，剩余节点作为测试集。评估指标为测试集的 Micro-F1 和 Macro-F1 。

   对于节点聚类任务，我们将学到的node embedding 作为聚类模型的输入。这里我们采用 Kmeans 算法作为聚类算法，然后采用 NMI 和 ARI 作为评估指标。

2. 下表给出了所有方法的评估结果，最佳结果以粗体突出显示。

   结论：

   • 大多数模型在多标签分类任务中表现良好，并得到较高的 Macro-F1 和 Micro-F1 指标。这是因为这四个选定领域的作者彼此完全不同，分类相对容易。

   • 尽管如此，HetGNN 在多标签分类和节点聚类方面仍然达到了最佳性能或者可比的性能。这证明了HetGNN 是有效的，它产生了针对节点分类和聚类任务更有效的node embedding 。

   

3. 此外，我们还通过 tensorflow embedding projector 来可视化四个领域作者的 embedding 。我们随机采样了 100 位作者，如下图所示分别位 2D 可视化和 3D 可视化。

   可以看到：同类别作者的 embedding 紧密地聚集在一起，从而证明了学到的node embedding 的有效性。

   

1.2.4 inductive 节点分类&聚类

1. 该任务的配置和之前的节点分类&聚类任务类似，不同之处在于：我们对 A-II 数据集进行按年份拆分，拆分年份为 2013，然后将 2013 年以及之前的数据作为训练集、之后的数据作为测试集。

   我们用训练集中的数据来训练模型并得到训练集中节点的 embedding，然后用训练好的模型来推断测试集中新节点的 embedding 。最后我们使用推断的新node embedding 来作为分类和聚类模型的输入。

   注：逻辑回归分类器使用训练集中的节点来训练。

2. 下表给出了inductive 节点分类和聚类任务的结果，其中最佳结果以粗体显示。

   结论：

   • 大多数模型在inductive 多标签分类任务中表现良好，并得到较高的 Macro-F1 和 Micro-F1 指标。这是因为这四个选定领域的作者彼此完全不同，分类相对容易。

     尽管如此，HetGNN 在 inductive 多标签分类任务中仍然达到了最佳性能或者可比的性能

   • HetGNN 在inductive 节点聚类任务中优于所有其它方法。

   结果表明HetGNN 模型可以有效地推断新节点的 embedding 。

   

1.2.5 消融研究

1. 我们考察了HetGNN 模型的几种变体：

   • No-Neigh：直接使用异质内容编码来表示每个节点的 embedding，不考虑邻居信息。即：

     $${\overrightarrow{\mathbf{h}}}_v={\overrightarrow{\mathbf{z}}}_v$$

   • Content-FC：使用全连接层来作为异质内容编码器，从而代替 Bi-LSTM 。

   • Type-FC：使用全连接层来融合不同邻居类型的 embedding，而不是 BiLSTM + attention 。

   下图报告了 A-II 数据集（训练集--测试集拆分年份 2013）上链接预测和节点推荐的结果。

   结论：

   • 大多数情况下，HetGNN 性能优于 No-Neigh，这表明聚合邻域信息对于生成更好的node embedding 是有效的。

   • HetGNN 优于 Content-FC，这表明基于 Bi-LSTM 的内容编码要比浅层编码器（如全连接层）要更好，Bi-LSTM 可以捕获深度的内容特征交互。

   • HetGNN 优于 Type-FC，这表明在捕获节点类型的影响方面，基于 attention 机制要优于全连接层。

   

1.2.6 参数敏感性

1. 我们考察 HetGNN 链接预测和推荐的性能随 embedding 维度 $d$$d$ 的影响。我们在 A-II 训练集上评估，训练集--测试集拆分年份位 2013 。当固定采样邻居规模（设为 23），我们选择不同的 $d\in \{8,16,32,64,128,256\}$$d\in \{8,16,32,64,128,256\}$ 。

   结论：当 $d$$d$ 从 8 增加到 256 时，所有指标都会增加，因为学到了更好的 embedding 。但是 $d$$d$ 进一步增加时，性能变得不变或者更差，这可能是因为过拟合。

   

2. 我们考察 HetGNN 链接预测和推荐的性能随样本邻域大小的影响。我们在 A-II 训练集上评估，训练集--测试集拆分年份为 2013 。当固定 embedding 维度 $d=128$$d=128$ 时，我们选择不同的邻居采样规模，不同采样规模选择不同的邻居节点类型（即选择不同的top $k_t$$k_t$ ）：

   6 = 2 (author) + 2 (paper) + 2 (venue)
   12= 5 (author) + 5 (paper) + 2 (venue)
   17 = 7 (author) + 7 (paper) + 3(venue)
   23 = 10 (author) + 10 (paper) + 3 (venue)
   28 = 12 (author) + 12 (paper) + 4 (venue)
   34 = 15 (author) + 15 (paper) + 4 (venue)
   

   结论：当邻域大小从 6 增加到 34 时，所有指标都会增加，这是因为考虑了更多的邻域信息。但是当邻域规模超过某个值时，性能可能会缓缓降低，这可能是因为涉及到不相关的（噪音）邻居导致。最佳邻域大小为 20 ~ 30 。